Problem statement: zenit17kkf

Faktoriál vs. Mocnina

Počet bodov: 25, časový limit: 1000ms

Koho baví pozerať sa na futbalový zápas v miestnej krčme? Sama teda nie. Ten má oveľa väčšie nadšenie pre matematiku a tak chodí sledovať pravidelné súboje funkcií. Tento týždeň sa odohrá dlho očakávaný zápas medzi tímami FKS (Faktoriály Ktoré Súperia) a KMS (Kráľovské Mocniny Súbojové). V niekoľkých kolách oba tímy vyšlú niektorého svojho bojovníka - bojovníka FKS nazveme \(n\) a bojovníka KMS zase \(x\).

Samo si na súboje rád vsádza. Aby sa však vedel rozhodnúť, na koho vsadiť, potreboval by nejako odhadnúť relatívnu silu bojovníkov. Ako dobrý ukazovateľ sily sa rozhodol použiť koeficient \(k\) s nasledovným významom: \(k\) je najväčšie celé číslo, ktorým vieme \(n!\) bezozvyšku vydeliť \(x^k\).

Sama však baví stávkovanie, nie určovanie koeficientov. Pomôžte mu!

Vstup a výstup

V jedinom riadku vstupu sú dve celé čísla \(n\) a \(x\).

Vypíšte najväčšie nezáporné celé \(k\) také, že \(x^k\) delí \(n!\).

Sú tri sady vstupov s nasledovnými obmedzeniami:

\(2 \leq x,n \leq 20\)

\(2 \leq x,n \leq 10^6\)

\(2 \leq x \leq 10^{12}\), \(2 \leq n \leq 10^{18}\)

Príklady

Input:

18 12

Output:

8

Input:

20 47

Output:

0